package com.dmall.list;

/**
 * 循环双向链表
 * @author xiao1.wang@dmall.com
 * @date 2019-07-16 23:29:02
 * @param <E> 泛型
 */
public class LoopTwoWayLinkedList<E> {

    private Node dummyHead, tail;
    private int size;

    public LoopTwoWayLinkedList() {
        dummyHead = new Node();
        tail = new Node();
        dummyHead.next = tail;
        dummyHead.prev = tail;
        tail.prev = dummyHead;
        tail.next = dummyHead;
        this.size = 0;
    }

    private class Node {
        public E e;
        public Node next;
        public Node prev;

        public Node(E e, Node next, Node prev) {
            this.e = e;
            this.next = next;
            this.prev = prev;
        }

        public Node(E e) {
            this(e, null, null);
        }

        public Node() {
            this(null, null, null);
        }

        @Override
        public String toString() {
            return e != null ? e.toString() : "NULL";
        }
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void add(int index, E e) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Index is illegal.");
        }

        if (index <= getSize() / 2) {
            // 在前半部分
            Node prev = dummyHead;
            for (int i = 0; i < index; i++) {
                prev = prev.next;
            }

            Node node = new Node(e);

            node.next = prev.next;
            prev.next = node;
            node.prev = prev;
            node.next.prev = node;
        } else {
            // 在后半部分
            Node cur = tail;
            for (int i = 0; i < size - index; i++) {
                cur = cur.prev;
            }
            Node node = new Node(e);
            node.prev = cur.prev;
            cur.prev.next = node;
            node.next = cur;
            cur.prev = node;
        }

        size ++;
    }

    public void addFirst(E e) {
        this.add(0, e);
    }

    public void addLast(E e) {
        this.add(size, e);
    }

    public E get(int index) {
        if (index < 0 || index > size - 1) {
            throw new IllegalArgumentException("Index is illegal.");
        }
        Node cur = dummyHead.next;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.e;
    }

    public E getFirst() {
        return this.get(0);
    }

    public E getLast() {
        return this.get(size - 1);
    }

    public E set(int index, E newData) {
        if (index < 0 || index > size - 1) {
            throw new IllegalArgumentException("Index is illegal.");
        }
        Node cur = dummyHead.next;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        E result = cur.e;
        cur.e = newData;
        return result;
    }

    public boolean contains(E e) {
        Node cur = dummyHead.next;
        while (cur != null) {
            if (cur.e.equals(e)) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    public E remove(int index) {
        if (index < 0 || index > size - 1) {
            throw new IllegalArgumentException("Index is illegal.");
        }
        E result;
        Node delNode;
        if (index <= getSize() / 2) {
            delNode = dummyHead.next;
            for (int i = 0; i < index; i++) {
                delNode = delNode.next;
            }

        } else {
            // 在后半部分
            delNode = tail;
            for (int i = 0; i < size - index; i++) {
                delNode = delNode.prev;
            }
        }
        result = delNode.e;
        delNode.prev.next = delNode.next;
        delNode.next.prev = delNode.prev;
        size --;
        return result;
    }

    public E removeFirst() {
        return this.remove(0);
    }

    public E removeLast() {
        return this.remove(size - 1);
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        Node cur = dummyHead.next;
        while (cur != tail) {
            res.append(cur.e).append("⇄");
            cur = cur.next;
        }
        res.append("NULL");
        return res.toString();
    }
}
